package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/20.
 * 给定一棵二叉搜索树，请找出其中的第k小的结点。
 * 例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。
 */
public class TreeKthNode {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }
    TreeNode KthNode(TreeNode pRoot, int k){
        if (pRoot == null || k == 0){
            return null;
        }
        return helper(pRoot, k);
    }

    private static TreeNode helper(TreeNode node, int k){
        TreeNode res = null;
        if (node.left != null){
            res = helper(node.left, k);
        }

        if (node != null){
            if (res == null){
                if (k == 1){
                    res = node;
                }
                k--;
            }
        }

        if (res == null && res.right != null){
            res = helper(node.right, k);
        }
        return res;
    }
}
